#ifndef treeh
#define treeh

#include "comparator.h"
#include "list.h"
struct empty_tree
{
};

template<int value_, typename left_, typename right_> struct tree
{
   static const int value = value_;
   typedef left_ left;
   typedef right_ right;
};

template<bool to_left, int value_, typename T> struct if_
{
};

template<int value_, typename tree_> struct add
{
   typedef
      typename if_<
         comparator<value_, tree_::value>::value,
         value_,
         tree_
      >::type type;
};

template<int value_, typename tree_> struct if_<true, value_, tree_>
{
   typedef 
      tree<
         tree_::value, 
         typename add<
            value_, 
            typename tree_::left
         >::type, 
         typename tree_::right
      > type;
};

template<int value_, typename tree_> struct if_<false, value_, tree_>
{
   typedef tree<
      tree_::value, 
      typename tree_::left, 
      typename add<
         value_,
         typename tree_::right
      >::type
   > type;
};

template<int value_> struct add<value_, empty_tree>
{
   typedef tree<value_, empty_tree, empty_tree> type;
};

template<typename tree_> struct tree_to_list
{
   typedef typename concat<
      typename tree_to_list<
         typename tree_::left
      >::type,
      list<
         tree_::value, 
         typename tree_to_list<
            typename tree_::right
         >::type
      >
   >::type type;
};

template<> struct tree_to_list<empty_tree>
{
   typedef empty_list type;
};

template<typename list_> struct list_to_tree
{
   typedef typename add<
      list_::head, 
      typename list_to_tree<
         typename list_::tail
      >::type
   >::type type;
};

template<> struct list_to_tree<empty_list>
{
   typedef empty_tree type;
};

#endif
